package com.cty._01_Base._13_RobotMove;

/**
 * @Auther: cty
 * @Date: 2020/7/2 11:24
 * @Description: 面试题13：机器人的运动范围
 * 题目：地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动，它
 * 每一次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和
 * 大于k的格子。例如，当k为18时，机器人能够进入方格(35, 37)，因为3+5+3+7=18。
 * 但它不能进入方格(35, 38)，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 * @version: 1.0
 */
public class RobotMove {

    /**
     * 统计机器人的活动格子数
     * @param threshold
     * @param rows
     * @param cols
     * @return
     */
    public static int moveCount(int threshold, int rows, int cols){
        if(threshold<0 || rows<=0 || cols<=0)
            return 0;

        boolean[] visited = new boolean[rows * cols];
        return moveCountCore(threshold,rows,cols,visited,0,0);
    }

    /**
     * 回溯法统计机器人活动格子数
     * @return
     */
    private static int moveCountCore(int threshold, int rows, int cols,
                                     boolean[] visited, int row, int col){
        int count = 0;
        if(check(threshold,rows,cols,visited,row,col)){
            visited[row*cols + col] = true;

            count = 1 + moveCountCore(threshold,rows,cols,visited,row-1,col)
                    + moveCountCore(threshold,rows,cols,visited,row+1,col)
                    + moveCountCore(threshold,rows,cols,visited,row,col-1)
                    + moveCountCore(threshold,rows,cols,visited,row,col+1);
        }
        return count;
    }

    // 检查当前格子是否满足条件
    private static boolean check(int threshold, int rows, int cols,
                                 boolean[] visited, int row, int col){
        if(row>=0 && row<rows && col>=0 && col<cols
                && !visited[row*cols+col]
                && getDigitSum(row)+getDigitSum(col)<=threshold)
            return true;
        return false;
    }

    // 获取数字位数和
    private static int getDigitSum(int num){
        int sum = 0;
        while(num > 0){
            sum += num%10;
            num /= 10;
        }
        return sum;
    }

}  // end class
